package org.example.myleet.p714;

/**
 * DP
 * 分持有的状态和空仓状态，分别记录每天收盘时每种状态的最大资产数
 * 持有状态可能来自保持昨天的持有状态，也可能来自昨天空仓而按今天买入
 * 空仓状态可能来自保持昨天的空仓状态，也可能来自昨天持有的资产按今天的价格进行卖出并扣除手续费
 * 递推公式
 * dp1[i] = Math.max(dp2[i-1] - prices[i], dp1[i-1]);
 * dp2[i] = Math.max(dp1[i-1] + prices[i] - fee, dp2[i-1]);
 */
public class Solution {
    /**
     * 7 ms
     */
//    public int maxProfit(int[] prices, int fee) {
//        int[] dp1 = new int[prices.length];
//        int[] dp2 = new int[prices.length];
//        dp1[0] = -prices[0];
//        for (int i=1; i<prices.length; i++) {
//            dp1[i] = Math.max(dp2[i-1] - prices[i], dp1[i-1]);
//            dp2[i] = Math.max(dp1[i-1] + prices[i] - fee, dp2[i-1]);
//        }
//        return dp2[prices.length-1];
//    }

    /**
     * dp 的每次迭代都只依赖于前一个, 就没必要用数组把它们都存下来
     * 5 ms
     */
    public int maxProfit(int[] prices, int fee) {
        int dp1 = -prices[0], dp2 = 0;
        for (int i=1; i<prices.length; i++) {
            int t = dp1;
            dp1 = Math.max(dp2 - prices[i], dp1);
            dp2 = Math.max(t + prices[i] - fee, dp2);
        }
        return dp2;
    }
}
